package com.labuladong;

import java.util.*;

/**
 * 项目名称: java_algorithm
 * @ClassName OpenTheTurntableLock
 * @Description 打开转盘锁
 * @Author huipanxing huipanxing@chinasofti.com   @Date 2022/6/24 11:20
 */
public class OpenTheTurntableLock {

    public static void main(String[] args) {
        String [] deadheads=new String[]{"5435","6546","7567"};
        String target="8451";
        int openLock = openLock(deadheads, target);
        System.out.println(openLock);
    }

    public static int openLock(String[] deadheads,String target){
        String initialPassword="0000";
        List<String> deadList = Arrays.asList(deadheads);
        //存入走过的路
        List<String> visited=new ArrayList<>();
        //bfs队列
        Queue<String> queue=new LinkedList<>();
        int step=0;
        queue.offer(initialPassword);
        visited.add(initialPassword);
        while (!queue.isEmpty()){
            int size = queue.size();
            //必须一层一层遍历
            for (int i=0;i<size;i++){
                String poll = queue.poll();
                if (deadList.contains(poll)){
                    continue;
                }
                if (target.equals(poll)){
                    return step;
                }

                for (int j=0;j<initialPassword.length();j++){
                    String plusOne = plusOne(poll, j);
                    if (!visited.contains(plusOne)){
                        visited.add(plusOne);
                        queue.offer(plusOne);
                    }
                    String minusOne = minusOne(poll, j);
                    if (!visited.contains(minusOne)){
                        visited.add(minusOne);
                        queue.offer(minusOne);
                    }
                }
            }
            step++;
        }
        return -1;
    }

    //将 s[j] 向上拨动⼀次
    public static String plusOne(String s,int j){
        char[] ch = s.toCharArray();
        if (ch[j]=='9'){
            ch[j]='0';
        }else {
            ch[j]+=1;
        }
        return new String(ch);
    }

    //将 s[j] 向下拨动⼀次
    public static String minusOne(String s,int j){
        char[] ch = s.toCharArray();
        if (ch[j]=='0'){
            ch[j]='9';
        }else {
            ch[j]-=1;
        }
        return new String(ch);
    }
}
